The present invention relates generally to improved information retrieval systems for images and other nonstructure data, and more particularly to converting a query with fuzzy specifications of one or more objects and spatial or temporal relationships between different objects into a set of subgoals, organizing the entire search space into blocks blocks according to the set of subgoals; and processing the query blocks in the order of likelihood of satisfying, the final constraints without possible false dismissal.
It is becoming increasingly important for multimedia databases to provide capabilities for content-based retrieval of composite objects. Composite objects consist of several simple objects which have feature, spatial, temporal, semantic attributes, and spatial and temporal relationships between them. Recent methods for retrieving images and videos by content from large archives utilize feature descriptions and feature comparison metrics in order to index the visual information. Examples of such content-based retrieval systems include the IBM Query by Image Content (QBIC) system detailed in xe2x80x9cQuery by image and video content: The {IQBI} system.xe2x80x9d by M. Flickner, et al in xe2x80x9cIEEE Computerxe2x80x9d, 28(9):23-32. (September 1995); the Virage visual information retrieval system detailed in xe2x80x9cVirage image search engine: an open framework for image management,xe2x80x9d by J. Bach, et al in xe2x80x9cSymposium on Electronic Imaging: Science and Technologyxe2x80x94Storage and Retrieval for Image and Video Databases {IV}xe2x80x9d, volume 2670, pages 76-87. (1996), the MIT Photobook, detailed in xe2x80x9cTools for content-based manipulation of image databases,xe2x80x9d by A. Pentland, et al in xe2x80x9cProceedings of the SPIE Storage and Retrieval Image and Video Databases IIxe2x80x9d, (February 1994); the Alexandria project at UCSB detailed in xe2x80x9cTexture features for browsing and retrieval of image data,xe2x80x9d by B. S. Manjunath and W. Y. Ma, xe2x80x9cIEEE Trans. Pattern Analysis Machine Intell. Special Issue on Digital Librariesxe2x80x9d, 8 (1996) and in xe2x80x9cDimensionality reduction using multidimensional scaling for image search,xe2x80x9d by M. Beatty and B. S. Manjunath, published in the xe2x80x9cProc. IEEE International Conference on Image Processingxe2x80x9d (October 1997); and the IBM/NASA Satellite Image Retrieval System detailed xe2x80x9cProgressive content-based retrieval from distributed image/video databases,xe2x80x9d by in C.-S. Li, V. Castelli, and L. Bergman in the xe2x80x9cProceedings of the International Symposium of Circuit and Systemxe2x80x9d, IEEE (1997).
It is becoming increasingly important for multimedia databases to provide capabilities for content-based retrieval of composite objects. Composite objects consist of several simple objects which have features, spatial, temporal and semantic attributes, and spatial and temporal relationships between them. The need for compound search queries frequently arises in various scientific and engineering applications, for processing such as the following:
Retrieve those Synthetic Aperture Radar (SAR) Satellite images and identify those regions in the images with texture type (e.g., ice) similar to the search target,
Retrieve those one-meter resolution satellite images and identify those regions in the images with spectral features (e.g., crop) similar to the search target,
Retrieve those LANDSAT Thematic Mapper (TM) satellite images and identify those regions in the images with a combination of spectral and texture features (e.g., indicative of terrain type) similar to the search target.
These scenarios frequently arise in the following applications:
Environmental epidemiology: wherein there is a need to retrieve locations of houses which are vulnerable to epidemic diseases such as Hantavirus and Denge fever based on a combination of environmental factors (e.g. isolated houses that are near bushes or wetlands), and weather patterns (e.g. a wet summer followed by a dry summer);
Precision farming: for (1) retrieving locations of cauliflower crop developments that are exposed to clubroot, which is a soil-borne disease that infects cauliflower crop, where cauliflower and clubroot are recognized spectral signature, and exposure results from their spatial and temporal proximity; and (2) retrieving those fields which have abnormal irrigation, (3) Retrieve those regions which have higher than normal soil temperature;
Precision forestry: for (1) calculating areas of forests that have been damaged by hurricane, forest fire, or storms, and (2) estimating the amount of the yield of a particular forest;
Petroleum exploration: where there is a need to retrieve those regions which exemplify specific characteristics in the collection of seismic data, core images, and other sensory data;
Insurance: for (1) retrieving those regions which may require immediate attention due to natural disasters such as earthquake, forest fire, hurricane, and tornadoes, and (2) retrieving those regions have higher than normal claim rate (or amount) that are correlated to the geographyxe2x80x94close to coastal regions, close to mountains, in high crime rate regions, etc.;
Medical image diagnosis: for retrieval of all MRI images of brains that have tumors located within the hypothalamus, which tumors are characterized by shape and texture, and the hypothalamus is characterized by shape and spatial location within the brain;
Real estate marketing: to retrieve all houses that are near a lake (color and texture), have a wooded yard (texture) and are within 100 miles of skiing (mountains are also given by texture); and
Interior design: for retrieval of all images of patterned carpets which consist of a specific spatial arrangement of color and texture primitives.
Until recently, content-based query and spatial query paradigms have been largely distinct. On one hand, there has been extensive investigation of using logical representations to facilitate efficient processing of spatial and temporal queries of symbolic images (see: xe2x80x9cDesign and Evaluation of Algorithms for Image Retrieval by Spatial Similarityxe2x80x9d, by V. N. Gudivada and V. V. Raghavan, in the xe2x80x9cACM Trans. on Information Systemsxe2x80x9d, Vol. 13, No. 2 (April 1995); xe2x80x9cIconic Indexing by {2-D} Stringsxe2x80x9d, by S.-K. Chang and Q. Y. Shi and C. Y. Yan, xe2x80x9cIEEE Trans. on Pattern Recognition and Machine Intelligencexe2x80x9d, Vol. 9, No. 3, pp. 413-428 (May 1987)), and videos (xe2x80x9cOVID: Design and Implementation on a Video-Object Database Systemxe2x80x9d, by E. Oomoto and K. Tanaka, xe2x80x9cTrans. on Knowledge and Data Engineeringxe2x80x9d, vol. 5 (August 1993)). The various logical representations such as 2D-strings, the "THgr"-R representation, and the spatial orientation graph (SOG) allow indexing and retrieval based upon spatial and temporal relationships.
On the other hand, content-based image retrieval systems, such as Virage, Photobook and QBIC, allow querying based upon image features. Examples of the visual features supported by these systems include color, texture, shape, edge, and so forth.
The integration of content-based and spatial image query methods is only recently begun to be investigated (see the above-referenced publications of Li et al, Smith and Chang, and, xe2x80x9cRetrieval by content in symbolic-image databasesxe2x80x9d, by A. Soffer and H. Samet, in the xe2x80x9cSymposium on Electronic Imaging: Science and Technologyxe2x80x94Storage and Retrieval for Image and Video Databases IVxe2x80x3, 2670, pp144-155 (1996)xe2x80x9d; xe2x80x9cContent-Based Indexing of Spatial Objects in Digital Librariesxe2x80x9d, by S.-F Chang et al; S.-S. Chen, in the xe2x80x9cJournal of Visual Communication and Image Representationxe2x80x9d, 1, pp.16-27 (March 1996); E, xe2x80x9cSimilarity Searching in Large Image Databasesxe2x80x9d, by. G. M. Petrakis and C. Faloutsos, xe2x80x9cDepartment of Computer Science, University of Marylandxe2x80x9d, 3388, (1995).) The SaFe spatial and feature image query engine computes the spatial and feature queries by decomposing the composite query into parallel, content-based region queries. After the joining the results, the spatial relationships are evaluated only for the surviving images using query-time 2D-string projection and comparison. SaFe is also being extended to spatial and temporal querying of video (see: xe2x80x9cVideoQ: An Automated Content Based Video Search System Using Visual Cuesxe2x80x9d, by S.-F. Chang, et al in the xe2x80x9cProc. ACM Multimedia ""97xe2x80x9d, ACM, (November, 1997)). In the IBM/NASA satellite image retrieval system, a framework is provided for the querying of earth observation imagery by incorporating semantic and feature-based object descriptions into a rule-based spatial query framework.
The difficulty in content-based querying of composite objects results from the combinatorial explosion in candidate composite objects, which number on the order of O(LK) for composites of K simple objects selected from a database of L simple objects. Furthermore, content-based querying requires significant computational processing in retrieving features from the database and computing feature similarities. In order to design a sufficiently scalable and powerful solution, the system needs to efficiently manage the search process in order to respond to the queries.
In accordance with the aforementioned needs, the present invention is directed to an improved apparatus and method to generate an efficient linear ordering of the component descriptions (sub-goals) of the composite object (query-goal) and generates a sequential query processing schedule. Since the content-based components of the query involves the assessment of spatial, temporal and feature similarities, the system builds and maintains an overall similarity score between each candidate composite retrieved from the database and the query composite object. The inventive system selects the candidate composite objects for evaluation in a best-first search. Since the similarity scores are monotonically non-decreasing, by partially back-tracking through only the stages which involve content-based querying, the inventive method finds the optimal solution in an efficient manner.